Example

Suppose we have an LRU cache with capacity = 3, and we perform the following operations:

put(1, A)     // cache: {1:A}
put(2, B)     // cache: {1:A, 2:B}
put(3, C)     // cache: {1:A, 2:B, 3:C}
get(1)        // access key 1 → makes it most recently used
put(4, D)     // key 2 is least recently used → evict it

Final cache state: {3:C, 1:A, 4:D} (in order of usage from least to most recent)

In this chapter, we will explore the low level design of a LRU cache.

Lets start by clarifying the requirements:

1. Clarifying Requirements

Before starting the design, it's important to ask thoughtful questions to uncover hidden assumptions, clarify ambiguities, and define the system's scope more precisely.

Here is an example of how a discussion between the candidate and the interviewer might unfold:

After gathering the details, we can summarize the key system requirements.

1.1 Functional Requirements

1.2 Non-Functional Requirements

After the requirements are clear, the next step is to identify the core entities that we will form the foundation of our design.

2. Identifying Core Entities

Unlike systems that model real-world concepts (such as users, products, or bookings), the design of an LRU Cache is centered around choosing the right data structures and internal abstractions to achieve the required functionality and performance specifically, O(1) time complexity for both get and put operations.

The core challenge here is twofold:

Let’s break this down.

The Need for Fast Lookup

To efficiently retrieve values by key, we need a data structure that supports constant-time key access.

The natural choice for this is a Hash Map (or Dictionary) since it provides O(1) average-case lookup and update.

The Need for Fast Ordering

The second challenge is maintaining the recency order of cache entries so we can:

An array or a list won’t work, because inserting or moving elements from the middle involves shifting which is an O(N) operation.

Instead, we use a Doubly Linked List since it allows fast removal and insertion of nodes from any position.

Each node maintains references to both its prev and next nodes, allowing us to:

Combining Both Structures

The magic of achieving O(1) for both get and put lies in combining a hash map and a doubly linked list:

This combination gives us the best of both worlds:

Additional Core Entities

Beyond the HashMap and Doubly Linked List, we need two more classes to encapsulate and organize our logic:

These entities form the core abstractions of our LRU Cache. They enable the system to maintain a fixed-size cache, support constant-time access and updates, and evict the least recently used entry when necessary.

3. Designing Classes and Relationships

Now that we’ve identified the core entities required to build an LRU Cache, the next step is to translate those entities into a well-structured class design.

This includes defining each class's attributes and responsibilities, establishing clear relationships among them, and visualizing the overall architecture through a class diagram.

Our goal is to ensure that the system remains modular, efficient, and easy to reason about all while satisfying the requirement of O(1) time complexity for both get and put operations.

3.1 Class Definitions

We’ll start with the simplest components and build up toward the core coordinating class.

Node<K, V>

Represents an individual entry in the cache, and also serves as a node in the doubly linked list.

Attributes:

Responsibility:

Stores key-value pairs and enables fast movement and removal in the doubly linked list through its pointers.

DoublyLinkedList<K, V>

A utility class that manages the MRU (Most Recently Used) to LRU (Least Recently Used) ordering of cache entries.

Attributes:

Methods:

Responsibility:

Maintains the usage order of cache entries and supports O(1) operations for insertion, movement, and removal.

LRUCache<K, V>

The main class that provides the public APIs (get and put) and manages the overall cache logic.

Attributes:

Methods:

get(K key): V

put(K key, V value): void

Responsibility:

Coordinates all cache operations, including lookup, insertion, eviction, and recency tracking.

3.2 Class Relationships

Composition ("has-a")

Association ("uses-a")

3.3 Full Class Diagram

4. Implementation

4.1 Node Class

1from typing import TypeVar, Generic, Optional
2
3K = TypeVar('K')
4V = TypeVar('V')
5
6class Node(Generic[K, V]):
7    def __init__(self, key: K, value: V):
8        self.key = key
9        self.value = value
10        self.prev: Optional['Node[K, V]'] = None
11        self.next: Optional['Node[K, V]'] = None

This is a generic doubly linked list node that stores:

This enables constant-time addition and removal of nodes from anywhere in the list, a key requirement for efficient LRU eviction.

4.2 DoublyLinkedList Class

1from typing import TypeVar, Generic, Optional
2from node import Node
3
4K = TypeVar('K')
5V = TypeVar('V')
6
7class DoublyLinkedList(Generic[K, V]):
8    def __init__(self):
9        self.head: Node[K, V] = Node(None, None)  # Dummy head
10        self.tail: Node[K, V] = Node(None, None)  # Dummy tail
11        self.head.next = self.tail
12        self.tail.prev = self.head
13
14    def add_first(self, node: Node[K, V]) -> None:
15        node.next = self.head.next
16        node.prev = self.head
17        self.head.next.prev = node
18        self.head.next = node
19
20    def remove(self, node: Node[K, V]) -> None:
21        node.prev.next = node.next
22        node.next.prev = node.prev
23
24    def move_to_front(self, node: Node[K, V]) -> None:
25        self.remove(node)
26        self.add_first(node)
27
28    def remove_last(self) -> Optional[Node[K, V]]:
29        if self.tail.prev == self.head:
30            return None
31        last = self.tail.prev
32        self.remove(last)
33        return last

Implements a doubly linked list with dummy head and tail nodes to simplify edge-case handling.

This list manages access order, with the head representing most recently used and the tail representing least recently used.

4.3 LRUCache Class

1import threading
2from typing import TypeVar, Generic, Optional, Dict
3
4K = TypeVar('K')
5V = TypeVar('V')
6
7class LRUCache(Generic[K, V]):
8    def __init__(self, capacity: int):
9        self.capacity = capacity
10        self.map: Dict[K, Node[K, V]] = {}
11        self.dll: DoublyLinkedList[K, V] = DoublyLinkedList()
12        self.lock = threading.Lock()
13
14    def get(self, key: K) -> Optional[V]:
15        with self.lock:
16            if key not in self.map:
17                return None
18            node = self.map[key]
19            self.dll.move_to_front(node)
20            return node.value
21
22    def put(self, key: K, value: V) -> None:
23        with self.lock:
24            if key in self.map:
25                node = self.map[key]
26                node.value = value
27                self.dll.move_to_front(node)
28            else:
29                if len(self.map) == self.capacity:
30                    lru = self.dll.remove_last()
31                    if lru is not None:
32                        del self.map[lru.key]
33                new_node = Node(key, value)
34                self.dll.add_first(new_node)
35                self.map[key] = new_node
36
37    def remove(self, key: K) -> None:
38        with self.lock:
39            if key not in self.map:
40                return
41            node = self.map[key]
42            self.dll.remove(node)
43            del self.map[key]

The LRUCache class uses two main data structures:

This ensures that both get() and put() operations run in O(1) time.

get() Method

If the key exists, the corresponding node is moved to the front of the list (most recently used), and its value is returned. If not found, returns null.

put() Method

This ensures LRU behavior while maintaining constant-time operations.

remove() Method

Allows explicit removal of an entry from the cache, updating both the list and the map.

Thread Safety: The get and put methods are marked as synchronized to ensure that the cache behaves correctly in a multi-threaded environment, preventing race conditions that could corrupt the state of the map and the list.

4.4 Usage Example

The demo code shows the LRUCache in action and illustrates the eviction policy.

1class LRUCacheDemo:
2    @staticmethod
3    def main():
4        cache: LRUCache[str, int] = LRUCache(3)
5
6        cache.put("a", 1)
7        cache.put("b", 2)
8        cache.put("c", 3)
9
10        # Accessing 'a' makes it the most recently used
11        print(cache.get("a"))  # 1
12
13        # Adding 'd' will cause 'b' (the current LRU item) to be evicted
14        cache.put("d", 4)
15
16        # Trying to get 'b' should now return None
17        print(cache.get("b"))  # None
18
19if __name__ == "__main__":
20    LRUCacheDemo.main()

5. Run and Test

6. Quiz